{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1、两数之和"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#暴力解\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    return [i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        dict = {}\n",
    "        dict[nums[0]] = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            tofind = target - nums[i]\n",
    "            if tofind in dict:\n",
    "                return [i,dict[tofind]]\n",
    "            else:\n",
    "                dict[nums[i]] = i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2、两数相加"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 == None:\n",
    "            return l2\n",
    "        if l2 == None:\n",
    "            return l1\n",
    "        dummy = ListNode(0)\n",
    "        p = dummy\n",
    "        carry = 0\n",
    "        while l1 and l2:\n",
    "            p.next = ListNode((l1.val + l2.val + carry) % 10)\n",
    "            carry = (l1.val + l2.val + carry) // 10\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "            p = p.next\n",
    "        if l2:\n",
    "            while l2:\n",
    "                p.next = ListNode((l2.val + carry) % 10)\n",
    "                carry = (l2.val + carry) // 10\n",
    "                l2 = l2.next\n",
    "                p = p.next\n",
    "        if l1:\n",
    "            while l1:\n",
    "                p.next = ListNode((l1.val + carry) % 10)\n",
    "                carry = (l1.val + carry ) // 10\n",
    "                l1 = l1.next\n",
    "                p = p.next\n",
    "        if carry == 1:\n",
    "            p.next = ListNode(1)\n",
    "\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3、无重复最长子串"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self,s):\n",
    "        start = -1\n",
    "        max = 0\n",
    "        d = {}\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            if s[i] in d and d[s[i]] > start:\n",
    "                start = d[s[i]]\n",
    "                d[s[i]] = i\n",
    "            else:\n",
    "                d[s[i]] = i\n",
    "                if i - start > max:\n",
    "                    max = i - start\n",
    "                    \n",
    "        return max\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4、寻找两个正序数组的中位数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "#O(m+n)\n",
    "def findMedianSortedArrays( nums1, nums2):\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        lst = [0] * (m+n)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i<m and j<n:\n",
    "            if nums1[i] <= nums2[j]:\n",
    "                lst[i+j] = nums1[i]\n",
    "                i = i + 1\n",
    "            else:\n",
    "                lst[i+j] = nums2[j]\n",
    "                j = j + 1\n",
    "        if i == m :\n",
    "            lst[i+j:] = nums2[j:]\n",
    "        if j == n:\n",
    "            lst[i+j:] = nums1[i:]\n",
    "        print(lst)\n",
    "        if (m+n)%2 ==0 :\n",
    "            return (lst[(m+n)//2]+lst[(m+n)//2-1])/2\n",
    "        else:\n",
    "            return lst[(m+n)//2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Olog(m+n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5、最长回文子串"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestPalindrome(s):\n",
    "     #两种判断条件\n",
    "     #DP动态规划\n",
    "    palindrome = ''\n",
    "    for i in range(len(s)):\n",
    "        len1 = len(getlongestpalindrome(s,i,i)):\n",
    "        \n",
    "        if len1 > len(palindrome):\n",
    "            palindrome = getlongestpalindrome(s,i,i)\n",
    "        \n",
    "        len2 = len(getlongestpalindrome(s,i,i+1))\n",
    "        \n",
    "        if len2 > len(palindrome):\n",
    "            palindrome = getlongestpalindrome(s,i,i+1)\n",
    "\n",
    "def getlongestpalindrome(s,l,r):\n",
    "    while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "        l = l - 1\n",
    "        r = r + 1\n",
    "    return s[l+1:r]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6、Z字形变换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1 or numRows >= len(s):\n",
    "            return s\n",
    "        rows = [[] for _ in range(numRows)]\n",
    "        i = 0\n",
    "        for string in s:\n",
    "            if i == 0:\n",
    "                flag = True\n",
    "            if i == numRows - 1:\n",
    "                flag = False\n",
    "            if flag == True:\n",
    "                rows[i].append(string)\n",
    "                i = i + 1\n",
    "            else:\n",
    "                rows[i].append(string)\n",
    "                i = i - 1\n",
    "        zig = ''\n",
    "        for row in rows:\n",
    "            zig  = zig+''.join(row)\n",
    "        return zig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convert(self, s: str, numRows: int) -> str:\n",
    "    if numRows == 1 or numRows >= len(s):\n",
    "        return s\n",
    "        \n",
    "    zigzag = ['' for x in range(numRows)]\n",
    "    row,step = 0,1\n",
    "    for crct in s:\n",
    "        zigzag[row] += crct\n",
    "        \n",
    "        if row == 0 :\n",
    "            step = 1\n",
    "        elif row == numRows - 1:\n",
    "            step = -1\n",
    "        \n",
    "        row = row + step\n",
    "    \n",
    "    return ''.join(zigzag)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7、整数反转"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        a = abs(x)\n",
    "        num = 0\n",
    "        while (a != 0):\n",
    "            temp = a % 10\n",
    "            num = num * 10 + temp\n",
    "            a = a // 10\n",
    "        if x > 0 and num < 2147483647:\n",
    "            return num\n",
    "        elif x < 0 and num <= 2147483647:\n",
    "            return -num\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8、字符串转换整数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def myAtoi(self, s: str) -> int:\n",
    "    stripS = str.strip()\n",
    "    \n",
    "    if stripS == '' or stripS == '-' or stripS == '+':\n",
    "        return 0\n",
    "    \n",
    "    s1 = re.match('[^\\d]+',(stripS.lstrip('-')).lstrip('+')) \n",
    "    if s1 != None:\n",
    "        return 0\n",
    "    else:\n",
    "        sl = re.search('\\-*\\+*\\d+',stripS).group()\n",
    "    \n",
    "    if s1[0:2] == '--' or s1[0:2] == '-+' or s1[0:2] = '++':\n",
    "        return 0\n",
    "    result = int(s1)\n",
    "    if result > 0:\n",
    "        return 2147483647 if result > 2147483647 else  result\n",
    "    else:\n",
    "        return -2147483648 if result < 2147483647 else result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9、回文整数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(x):\n",
    "    num = 0\n",
    "    a = abs(x)\n",
    "    while (a != 0):\n",
    "        temp = a % 10\n",
    "        num = num *10 +temp\n",
    "        a = int(a/10)\n",
    "    if x >= 0 and x == num:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10、正则表达式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    " def isMatch(self, s: str, p: str) -> bool:\n",
    "    cache = [[False]*(len(s)+1) for _ in range(len(p)+1)]\n",
    "    cache[0][0] = True\n",
    "    for i in range(1,len(p)):\n",
    "        cache[i+1][0] = cache[i-1][0] and p[i] == '*'\n",
    "    for i in range(len(p)):\n",
    "        for j in range(len(s)):\n",
    "            if p[i] == '*':\n",
    "                cache[i+1][j+1] = cache[i][j+1] or cache[i-1][j+1]\n",
    "                if p[i-1]==s[j] or p[i-1]=='.':\n",
    "                    cache[i+1][j+1] |= cache[i+1][j]\n",
    "            else:\n",
    "                cache[i+1][j+1] = cache[i][j] and (p[i]==s[j] or p[i]=='.')\n",
    "    return cache[-1][-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11、盛水最多的容器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15、三数之和"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def threeSum(self, nums):\n",
    "        length = len(nums)\n",
    "        result_lst = []\n",
    "        for i in range(length):\n",
    "            for j in range(i+1,length):\n",
    "                for k in range(j+1,length):\n",
    "                    if nums[i] + nums[j] + nums[k] == 0:\n",
    "                        elem = sorted([nums[i],nums[j],nums[k]])\n",
    "                        if elem not in result_lst:\n",
    "                            result_lst.append(elem)\n",
    "        return result_lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        length = len(nums)\n",
    "        if length < 3:\n",
    "            return []\n",
    "        nums_sort = sorted(nums)\n",
    "        if nums_sort[0] > 0:\n",
    "            return []\n",
    "        resutl_lst = []\n",
    "        for i in range(length-2):\n",
    "            j = i+1\n",
    "            k = length-1\n",
    "            while j < k:\n",
    "                if nums_sort[i]+nums_sort[j]+nums_sort[k] == 0:\n",
    "                    elem = [nums_sort[i],nums_sort[j],nums_sort[k]]\n",
    "                    if elem not in resutl_lst:\n",
    "                        resutl_lst.append(elem)\n",
    "                    j = j + 1\n",
    "                    k = k - 1\n",
    "                elif nums_sort[i]+nums_sort[j]+nums_sort[k] < 0:\n",
    "                    j = j + 1\n",
    "                else:\n",
    "                    k = k-1\n",
    "        return resutl_lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#大神解法\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        result = []\n",
    "        nums.sort()\n",
    "        for i in range(n-2):\n",
    "            if nums[i] + nums[i+1] + nums[i+2] >0:\n",
    "                break\n",
    "            if nums[i] + nums[n-2] + nums[n-1] < 0:\n",
    "                continue\n",
    "            if 0<i and nus[i] == nums[i-1]:\n",
    "                continue\n",
    "            l,r = i + 1,n-1\n",
    "            while l < r:\n",
    "                tmp = nums[i] + nums[l] + nums[r]\n",
    "                if tmp == 0:\n",
    "                    result.append([nums[i],nums[l],nums[r]])\n",
    "                    while l+1 <r and nums[l] = nums[l+1]:\n",
    "                        l += 1\n",
    "                    l += 1\n",
    "                    while l<r-1 and nums[r] == nums[r-2]:\n",
    "                        r -= 1\n",
    "                    r -= 1\n",
    "                elif tmp < 0:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return result\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 颜色分类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最小包含字串"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        d = dict(collections.Counter(t))    '{a:1,b:1,c:1}'\n",
    "        formed = 0\n",
    "        slow = 0\n",
    "        min_str = None\n",
    "        min_length = sys.maxsize - 1\n",
    "        for fast in range(len(s)):\n",
    "            ch = s[fast]\n",
    "            fast += 1\n",
    "            #不关心的单词\n",
    "            if ch not in d:\n",
    "                continue\n",
    "        \n",
    "            d[ch] -= 1\n",
    "            if d[ch] == 0:\n",
    "                formed += 1\n",
    "                \n",
    "            while formed == len(d) and slow <= fast:\n",
    "                curr_length = fast - slow\n",
    "                if curr_length < min_length:\n",
    "                    min_length = curr_length\n",
    "                    min_str = s[slow:fast]\n",
    "                \n",
    "                \n",
    "                ch = s[slow]\n",
    "                slow += 1\n",
    "                if ch not in d:\n",
    "                    continue\n",
    "                d[ch] += 1\n",
    "                if d[ch] == 1:\n",
    "                    formed -= 1\n",
    "    return min_str if min_str is not None else \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 环形链表2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "faker",
   "language": "python",
   "name": "faker"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
